The growing network of packet based routers and bridges used in the Internet and other packet networks in addition to the increased network speeds of routing packets, such as 10 Gigabits per second, as specified in Optical Carrier standard document OC-192, require more efficient handling of large databases having long lookup keys. Such efficient handling involves processing database table lookups at rates over 250 million searches per second (Msps), limiting memory footprint size of memory modules, and limiting the density of each individual memory module used. All of these requirements must be met at a reasonable cost and at low power consumption. When processing a packet through a router, large databases such as the Internet protocol traffic flow database (TDB) as well as the forwarding information database (FIB) represent major performance bottlenecks in the high speed Internet traffic routing application.
Among its various aspects, the present invention recognizes the need to efficiently perform modular reduction of long lookup keys to support advantageous memory management techniques as described in U.S. application Ser. No. 10/653,762 entitled “Methods and Apparatus for Data Storage and Retrieval” which was filed on Sep. 3, 2003.